package _动态规划系列.最长回文子串;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/1 16:17
 * <p>
 * 功能描述:
 */
public class Summary_0005 {

    /**
     * bacabd
     */
    public String longestPalindrome(String s) {
        int n = s.length();

        if (n < 2)
            return s;


        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        int start = 0;
        int curlen = 0;

        //按列来遍历的
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(j) == s.charAt(i)) {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }else {
                    dp[i][j] = false;
                }

                if (dp[i][j] == true) {
                    curlen = j - i + 1;
                    if (curlen > maxLen){
                        maxLen = curlen;
                        start = i;
                    }
                }
            }


        }

        return s.substring(start, start + maxLen);
    }


    /*------------------------------------双指针------------------------------------------*/
    public String longestPalindrome1(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0, 1);
        // 中心位置枚举到 len - 2 即可
        for (int i = 0; i < len - 1; i++) {
            //找到以 s[i] 为中心的回文串
            String oddStr = centerSpread(s, i, i);
            //找到以 s[i] 和 s[i+1] 为中心的回文串
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    private String centerSpread(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0 && j < len) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
        return s.substring(i + 1, j);
    }

    /*------------------------------------双指针------------------------------------------*/
}
